package dynamic_planning;

/**
 * @Author Yi Jun jie
 * @Date 2021/3/3 22:42
 * 474. 一和零
 * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
 * 请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
 * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
 *
 * 示例：
 * 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
 * 输出：4
 * 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
 * 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
 *
 * 输入：strs = ["10", "0", "1"], m = 1, n = 1
 * 输出：2
 * 解释：最大的子集是 {"0", "1"} ，所以答案是 2。
 */

public class LeetCode474 {
    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        System.out.println(findMaxFormTemple(strs, 5, 3));
    }

    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String s : strs) {
            int[] count = countzeroesones(s);
            for (int zeroes = m; zeroes >= count[0]; zeroes--)
                for (int ones = n; ones >= count[1]; ones--)
                    dp[zeroes][ones] = Math.max(1 + dp[zeroes - count[0]][ones - count[1]], dp[zeroes][ones]);
        }
        return dp[m][n];
    }

    public static int[] countzeroesones(String s) {
        int[] c = new int[2];
        for (int i = 0; i < s.length(); i++) {
            c[s.charAt(i) - '0']++;
        }
        return c;
    }

    //使用模板代码
    /**
     * 第一步，要明确两点，[状态]和[选择]。
     *
     * 状态有三个， [背包对1的容量]、[背包对0的容量]和 [可选择的字符串]；选择就是把字符串[装进背包]或者[不装进背包]。
     *
     * 明白了状态和选择，只要往这个框架套就完事儿了：
     *
     * for 状态1 in 状态1的所有取值：
     * for 状态2 in 状态2的所有取值：
     * for ...
     * dp[状态1][状态2][...] = 计算(选择1，选择2...)
     *
     * "10", "0001", "111001", "1", "0"     5 个 0     3 个 1
     */
    public static int findMaxFormTemple(String[] strs, int m, int n) {
        int strsNum = strs.length;
        int[][][] dp = new int[strsNum + 1][m + 1][n + 1];// int[6][6][4]
        for (int i = 1; i <= strsNum; i++) {
            int[] cnt = count(strs[i - 1]);//得到数组中每个元素中 0 和 1 的个数放进去
            for (int j = 0; j <= m; j++) {//0 的个数
                for (int k = 0; k <= n; k++) {//1 的个数
                    if (cnt[0] > j || cnt[1] > k) {//对个数进行比较
                        //如果你不能把这第 i 个物品装入背包
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        //如果你可以把这第 i 个物品装入了背包
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - cnt[0]][k - cnt[1]] + 1);
                    }
                }
            }
        }
        return dp[strsNum][m][n];
    }


    // cnt[0] = zeroNums, cnt[1] = oneNums
    public static int[] count(String str) {
        int[] cnt = new int[2];
        for (char c : str.toCharArray()) {
            cnt[c - '0']++;
        }
        return cnt;
    }
}
